package gold.gold02;

/**
 * 中等
 */
public class S0405合法二叉搜索树 {

    /**
     * 31, 时刻注意子树为null的判断。
     * 二叉查找树不光是左<中<右, 而且是指左子树的所有值小于根节点小于右子树的所有值。
     * 二叉搜索树的中序遍历会得到一个递增序列, 这是一个重要性质。
     */
    public boolean isValidBST(TreeNode root) {
        if(root == null) return true;
        return isValidHelp(root).isBST;
    }
    // node在调用的时候保证非空了。
    public S0405resultType isValidHelp(TreeNode node){
        S0405resultType resultTemp = null;
        if(node.left == null){
            if(node.right == null){
                resultTemp = new S0405resultType(node.val, node.val, true);
                return resultTemp;
            }
            S0405resultType temp2 = isValidHelp(node.right);
            resultTemp = new S0405resultType(node.val, temp2.maxVal, temp2.isBST && node.val < temp2.minVal);
            return resultTemp;
        }else{
            S0405resultType temp1 = isValidHelp(node.left);
            if(node.right == null){
                resultTemp = new S0405resultType(temp1.minVal, node.val, temp1.isBST && temp1.maxVal < node.val);
                return resultTemp;
            }else{
                // 左子树右子树都存在
                S0405resultType temp2 = isValidHelp(node.right);
                resultTemp =  new S0405resultType(temp1.minVal, temp2.maxVal,
                        temp1.isBST && temp2.isBST && temp1.maxVal < node.val && node.val < temp2.minVal);
                return resultTemp;
            }
        }
    }
    // 内部类中的private字段可以被访问到, 就不写getter了。同理, 这个其实也可以被一个int[]代替
    class S0405resultType{
        private int minVal;
        private int maxVal;
        private boolean isBST;
        S0405resultType(int minVal, int maxVal, boolean isBST){
            this.minVal = minVal;
            this.maxVal = maxVal;
            this.isBST = isBST;
        }
        @Override
        public String toString(){
            return "当前节点: 最小值" + minVal + "最大值" + maxVal + "是否合法 " + isBST;
        }
    }

    // 这种, 每次判断单个节点的时候, 都把当前节点的左右子树扫描了一边。因为是从n -> n*n, 基本时间都是0, 所以问题不大。
    // 个人觉得还是只遍历一次好一点。
    public boolean isValidBST2(TreeNode root) {
        if (root == null) return true;  //如果当前节点为空  则这一节点的子树满足BST性质  返回true
        TreeNode maxLeft = root.left, minRight = root.right;   //创建两个节点，分别表示当前节点左子树和右子树的最大节点
        // 找寻左子树中的最右（数值最大）节点
        //这里有一个前提假设：假设当前的树BST ，那么此时左子树的最大节点必然是最右边的节点
        while (maxLeft != null && maxLeft.right != null)
            maxLeft = maxLeft.right;
        // 找寻右子树中的最左（数值最小）节点
        //这里有一个前提假设：假设当前的树BST
        while (minRight != null && minRight.left != null)
            minRight = minRight.left;
        // 判断当前层是否满足BST的要求
        boolean ret = (maxLeft == null || maxLeft.val < root.val) && (minRight == null || root.val < minRight.val);
        // 进入左子树和右子树并判断是否合法   递归判断左右子树
        return  ret && isValidBST2(root.left) && isValidBST2(root.right);

    }

    // 妙妙, 注意到二叉搜索树的一个特征, 中序遍历的话, 按照遍历顺序来说, 节点值是递增的。
    // 如果总体符合中序遍历递增, 那么每个节点就都是中序遍历递增的, 那么这就是一个二叉搜索树。
    TreeNode pre ;
    public boolean isValidBST3(TreeNode root) {
        if(root == null) return true ;
        Boolean L = isValidBST3(root.left);
        // 这句话会严格按照中序遍历的顺序执行
        if(pre != null && pre.val >= root.val) return false ;
        pre = root ;
        Boolean R = isValidBST3(root.right) ;
        return L && R ;
    }


}
